LinkedList 落幕了吗？
hi 这是 dhl 的第 51 篇文章
个人微信: hi-dhl
近期，看到网上有小伙伴们在讨论 LinkedList 作者自己都不用 LinkedList，我特意从网上搜索了一下，结果真让我找到了。
https://twitter.com/joshbloch/status/583813919019573248
大神真的不用 LinkedList 了吗？我仔细扒了一下，如下图所示，大神的回复。
其实大神非常喜欢链表的数据结构，在 C 语言中是非常有用的。并且也非常认可 ArrayDeque 的实现，因为 ArrayDeque 作为栈使用时可能比 Stack 快，作为队列使用时可能比 LinkedList 快。
但是为什么不用 LinkedList 呢？LinkedList 基于双向链表实现的双端队列，链表 和 队列都是非常好的数据结构，但是 Java 中 LinkedList 存在性能问题，所以在实际项目中，很少会用到，先来一起了解一下 LinkedList 的特点。
LinkedList 特点
LinkedList是基于双向链表的结构来存储元素，所以长度没有限制，因此不存在扩容机制由于链表的内存地址是非连续的，所以只能从头部或者尾部查找元素，查询的时间复杂为 O(n)，但是 JDK 对LinkedList做了查找优化，当我们查找某个元素时，若index < (size / 2)，则从head往后查找，否则从tail开始往前查找 , 但是我们在计算时间复杂度的时候，常数项可以省略，故时间复杂度O(n)
Node<E> node(int index) {
// size >> 1 等价于 size / 2
if (index < (size >> 1)) {
// form head to tail
} else {
// form tail to head
}
}
链表通过指针去访问各个元素，所以插入、删除元素只需要更改指针指向即可，因此插入、删除的时间复杂度 O(1)它是非线程安全的集合
LinkedList 属于链式队列，与之相对应的 ArrayDeque 是基于数组实现的双端队列，ArrayDeque 和 LinkedList 数据结构的特点如下所示。
| 集合类型 | 数据结构 | 初始化及扩容 | 插入/删除时间复杂度 | 查询时间复杂度 | 是否是线程安全 |
|---|---|---|---|---|---|
| ArrayDeque | 循环数组 | 初始化：16 扩容：2 倍 | 0(n) | 0(1) | 否 |
| LinkedList | 双向链表 | 无 | 0(1) | 0(n) | 否 |
更多关于 ArrayDeque 和 LinkedList 的优缺点，在什么情况下使用，以及它们谁更快，请前往查看 图解 ArrayDeque 比 LinkedList 快。
了解完数据结构特点之后，接下来我们从两个方面分析为什么 LinkedList 存在性能问题。
LinkedList 存在的性能问题
从速度的角度：
ArrayDeque基于数组实现双端队列，而LinkedList基于双向链表实现双端队列，数组采用连续的内存地址空间，通过下标索引访问，链表是非连续的内存地址空间，通过指针访问，所以在寻址方面数组的效率高于链表。从内存的角度：虽然
LinkedList没有扩容的问题，但是插入元素的时候，需要创建一个Node对象, 换句话说每次都要执行new操作，当执行new操作的时候，其过程是非常慢的，会经历两个过程：类加载过程 、对象创建过程。如果类已经初始化了，直接执行对象的创建过程 对象的创建过程：在堆内存中开辟一块空间，给开辟空间分配一个地址，之后执行初始化，会执行 <init>()方法，初始化普通变量，调用普通代码块会先判断这个类是否已经初始化，如果没有初始化，会执行类的加载过程 类的加载过程：加载、验证、准备、解析、初始化等等阶段，之后会执行 <clinit>()方法，初始化静态变量，执行静态代码块等等类加载过程
对象创建过程
在上一篇文章 图解 ArrayDeque 比 LinkedList 快 从 速度 和 内存 两个方面分析了 ArrayDeque 的性能都比 LinkedList 要好，并结合实际的案例来验证，结果如下图所示。
在之前的文章中，我围绕着 LinkedList （栈、队列 等等）写了四篇文章，从不同的角度进行了分析。
为什么不推荐使用 Java 栈 不推荐使用了，为什么现在还在用 为什么推荐使用 Deque接口替换栈Stack 和 ArrayDeque 区别 栈的时间复杂度 性能低 破坏了原有的数据结构 效率比 Java 栈快 屏蔽掉无关的方法 栈的定义 栈的实现 栈的实战 为什么不推荐使用 Java 栈 JDK 推荐使用 ArrayDeque代替Stack真的合理吗大神不推荐使用 ArrayDeque代替Stack如何实现一个真正意义上的栈 ArrayDeque和LinkedList数据结构的特点？为什么 ArrayDeque比LinkedList快？主要来学习如何设计循环队列 JDK 源码是如何设计队列？ 队列的大小为什么要设置成 2 的整数次幂？ 位运算 效率比 非位运算 快多少？ ArrayDeque 的 2 的整数次幂计算逻辑和 HashMap 有什么区别？ 自己如何设计一个循环队列？
推荐阅读：
感谢大家帮忙 在看、点赞、分享 给身边更多的朋友
代码不止，文章不停
欢迎点击下方卡片关注我，查看最新技术文章
因微信公众号更改了推送机制
可能无法及时看到最新文章
将公众号设为 星标
或常为文章点 在看
即可及时收到最新内容
欢迎前往 博客 查看更多 Kotlin、Jetpack 、动画算法图解、系统源码分析等等文章。以及开源项目、LeetCode / 剑指 offer / 国内外大厂面试题 / 多线程 题解。
https://www.hi-dhl.com